package bintree.LeetCode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

//145. 二叉树的后序遍历——左右根
//public class Num145_postorder {
//    List<Integer> rep = new ArrayList<>();
//    public List<Integer> postorderTraversal(TreeNode root) {
//        if(root == null){
//            return rep;
//        }
//        postorderTraversal(root.left);
//        postorderTraversal(root.right);
//        rep.add(root.val);
//
//        return rep;
//    }
//}

//非递归写后续遍历

/**
 * 思路：1.先一路向左走到根儿~ 此时栈中栈顶就是第一个左子树为空的节点
 * 关键的问题就是我如何得知这个节点是第三次访问到?
 * 引入一个新的变量prev
 * prev称为上一个完全访问结束的节点。
 * 使用prev引用表示当前节点的右子树是否被处理完平~~
 * 若cur.right != null && cur.right == prev =>处理完毕
 * 最后—次访问cur节点。
 */
public class Num145_postorder {

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        TreeNode cur = root;
        Deque<TreeNode> stack = new ArrayDeque<>();
        //上一个完成出来完毕的节点
        TreeNode prev = null;
        while(cur != null || !stack.isEmpty()){
            //1.先一路向左走到底
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }//——1.左
            //2.查看当前栈顶元素的情况
            cur = stack.pop();//弹出
            //检查右子树的情况
            if(cur.right == null || cur.right == prev){//——3.根
                //此时右子树为空或者右子树已经被处理完毕
                //那么就可以放心的访问cuo节点值
                ret.add(cur.val);
                //cur节点就是最新的出来结束的节点
                prev = cur;
                //为了继续从栈中取出栈顶元素
                cur = null;//如果不置，循环一又会重新把cur压入栈中，死循环
            }else{//——2. 右
                //此时cur.right ！= null 且没有被访问过，继续访问右子树
                stack.push(cur);//把弹出来的cur重新压回栈中
                //继续访问右子树
                cur = cur.right;
            }

        }

        return ret;
    }
}